/*************************************************************************
 * File Name:    Distinct_Subsequences.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/4 11:37:24
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Distinct Subsequences
 |
 | Given a string S and a string T, count the number of distinct subsequences of T in S.
 |
 | A subsequence of a string is a new string which is formed from the original string
 | by deleting some (can be none) of the characters without disturbing the relative
 | positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
 |
 | Here is an example:
 | S = "rabbbit", T = "rabbit"
 |
 | Return 3.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int numDistinct(string S, string T)
    {
        int m = S.size();
        int n = T.size();
        int dp[m + 1][n + 1];
        
        memset(dp, 0, sizeof(dp));
        
        dp[0][0] = 1;
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                dp[i][j] += dp[i - 1][j];
                if (j > 0 && S[i - 1] == T[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

